package com.zwj.interview.哈希表;

import java.util.List;

/**
 * 给定一组范围在00：00至23：59的时间，求任意两个时间之间的最小时间差。
 * 例如，输入时间数组["23：50"，"23：59"，"00：00"]，"23：59"和"00：00"之间只有1分钟的间隔，是最小的时间差
 */
@Deprecated
public class 最小时间差 {

    /**
     * 一天有24小时，即1440分钟。如果用一个长度为1440的数组表示一天的时间，那么数组下标为0的位置对应时间00：00，
     * 下标为1的位置对应时间00：01，以此类推，下标为1439的位置对应23：59。数组中的每个元素是true或false的标识，
     * 表示对应的时间是否存在于输入的时间数组中
     */
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) {
            return 0;
        }
        //初始值都为0
        int[] times = new int[timePoints.size()];
        //将时间转化为分钟数，构建一个数组
        for (int i = 0; i < timePoints.size(); i++) {
            String[] time = timePoints.get(i).split(":");
            times[i] = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
        }
        int result = Integer.MAX_VALUE;
        //相邻的连个时间相减，这就是错位相减
        for (int i = 0; i < timePoints.size(); i++) {
            for (int j = i + 1; j < timePoints.size(); j++) {
                //比较两个相邻的时间的时间差，之所以需要减去1440，是因为会出现这种情况：["00：00"，"23：50"，"23：59"]
                /**
                 * 这里有一个特殊情况值得注意。如果把输入的时间数组["23：50"，"23：59"，"00：00"]排序，
                 * 就可以得到["00：00"，"23：50"，"23：59"]。时间00：00和23：50之间的间隔是1430分钟，
                 * 而23：50和23：59之间的间隔是9分钟。由于排序之后的第1个时间00：00也可能是第2天的00：00，
                 * 它和前一天的23：59之间的间隔只有1分钟。
                 * 也就是说，在计算最小时间差时，需要把排序之后的第1个时间当作第2天的时间（即加上24小时）与最后一个时间之间的间隔也考虑进去
                 */
                int time = Math.min(Math.abs(times[j] - times[i]), Math.abs(Math.abs(times[i] - times[j]) - 1440));
                result = Math.min(time, result);
            }
        }
        return result;
    }


}
